package seqlist.doublelinked;

public class DoubleLinkedList {
    private int size;
    private Node head;
    private Node tail;

    //增
    public void addFirst(int val){
        // 设置一个新节点，在new新节点时，就已经将node.prev = null, node.next = head 了
        Node node=new Node(null,val,head);

        if(head==null){
            // 头结点为空时，尾节点就是新建的节点node
            tail=node;
        }else {
            // 头结点为不为空时，连接头结点head 指向新节点node 的线
            head.prev=node;
        }
        // 链表头结点就指向新建的节点node
        head=node;
        size++;
    }
    public void addLast(int val){
        Node node=new Node(tail,val,null);
        if(tail==null){
            head=node;
        }else {
            tail.next=node;
        }
        tail=node;
        size++;
    }
    public void addIndex(int index,int val){
        if(index<0||index>size){
            System.out.println("add index illegal!");
        }else if(index==0){
            addFirst(val);
        }else if(index==size){
            addLast(val);
        }else {
            Node prev=node(index-1);
            Node node=new Node(prev,val,prev.next);
            prev.next.prev=node;
            prev.next=node;
            size++;
        }
    }

    //查
    public int get(int index){
        if(rangeIndex(index)){
            return node(index).val;
        }else {
            System.out.println("get index illegal!");
            return -1;
        }
    }

    //判断是否存在
    public boolean isExist(int val){
        for (Node x=head;x!=null;x=x.next) {
            if(x.val==val){
                return true;
            }
        }
        return false;
    }

    //改
    public void change(int index,int val){
        if(rangeIndex(index)){
            Node oldNode=node(index);
            oldNode.val=val;
        }else {
            System.out.println("get index illegal!");
        }
    }

    //删
    public void removeIndex(int index){
        if (rangeIndex(index)){
            Node node=node(index);
            unLink(node);
        }else {
            System.out.println("remove index illegal!");
        }
    }
    public void removeFirst(){
        removeIndex(0);
    }
    public void removeLast(){
        removeIndex(size-1);
    }
    public void removeValOnce(int val){
        for(Node x=head;x!=null;x=x.next){
            if(x.val==val){
                unLink(x);
            }
        }
    }
    public void removeValeAll(int val){
        for (Node x=head;x!=null;){
            if(x.val==val){
                Node node=x.next;
                unLink(x);
                x=node;
            }else {
                x=x.next;
            }
        }
    }

    //删除指定节点
    public void unLink(Node node){
        //分治思想
        Node prev= node.prev;
        Node next= node.next;
        if(prev==null){
            head=next;
        }else {
            prev.next=next;
            node.prev=null;
        }
        if(next==null){
            tail=prev;
        }else {
            next.prev=prev;
            node.next=null;
        }
        size--;
    }

    //判断合法性
    public boolean rangeIndex(int index){
        if(index<0||index>=size){
            return false;
        }else {
            return true;
        }
    }

    //得到索引节点
    public Node node(int index){
        Node ret=null;
        if(index<(size>>1)){
            ret=head;
            for (int i = 0; i < index; i++) {
                ret=ret.next;
            }
        }else {
            ret=tail;
            for (int i = size-1; i > index; i++) {
                ret=ret.prev;
            }
        }
        return ret;
}

    //输出
    public String toString(){
        String ret="";
        Node node=head;
        while (node!=null){
            ret+=node.val;
            ret+="->";
            node=node.next;
        }
        ret+="null";
        return ret;
    }
}

class Node{
    Node prev;
    int val;
    Node next;

    public Node(int val){
        this.val=val;
    }
    public Node(Node prev,int val,Node next){
        this.prev=prev;
        this.val=val;
        this.next=next;
    }
}
